class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
    if (!head) return true; // 空链表总是匹配
    if (!root) return false; // 空树无法匹配非空链表
    
    // 检查从当前树节点开始的路径是否匹配链表
    return dfs(head, root) || 
           isSubPath(head, root.left) || 
           isSubPath(head, root.right);
}

function dfs(listNode: ListNode | null, treeNode: TreeNode | null): boolean {
    if (!listNode) return true; // 链表已遍历完，匹配成功
    if (!treeNode) return false; // 树节点为空但链表还有节点，匹配失败
    
    // 当前节点值不匹配，直接返回false
    if (listNode.val !== treeNode.val) return false;
    
    // 继续匹配链表的下一个节点和树的左右子树
    return dfs(listNode.next, treeNode.left) || 
           dfs(listNode.next, treeNode.right);
}